package com.david.learning.algorithm;

import java.util.List;
import java.util.ArrayList;

public class LineOrder{
	public static Line[] merge(Line[] input){
		List<Line> result = new ArrayList<Line>();
		Line aLine  = new Line(input[0].getStart(), input[0].getEnd());
		result.add(aLine);
		for (int i = 0; i<input.length; i++) {
			if (input[i].getStart() >= aLine.getStart() && input[i].getStart() <= aLine.getEnd()
				&& input[i].getEnd() >= aLine.getEnd()) {
				aLine.setEnd(input[i].getEnd());											
			}else if ( input[i].getStart() > aLine.getEnd()){
				aLine = new Line(input[i].getStart(),input[i].getEnd());
				result.add(aLine);				
			}			
		}
		return (Line[])(result.toArray(new Line[result.size()]));			
	}

	public static Line[] order(Line[] input){
		for(int i = 0; i<input.length;i++){
			for (int j = i+1; j<input.length; j++ ) {
				if (input[i].getStart()>input[j].getStart()) {
				    	switchElements(input, i, j);
				}else if (input[i].getStart()==input[j].getStart() && input[i].getEnd()>input[j].getEnd()) {
				    	switchElements(input, i, j);
				}
			}
		}
		return input;
	}
	
	public static Line[] orderByBubble(Line[] input){
		for(int i=0;i<input.length;i++){
			for (int j = i; j < input.length-1 ; j++) {
				if(input[j].getStart()>input[j+1].getStart()){
					switchElements(input, j, j+1);
				}else if(input[j].getStart() == input[j+1].getStart() && input[j].getEnd() > input[j+1].getEnd()){
					switchElements(input, j, j+1);
				}
			}
		}
		return input;
	}
	
	public static Line[] orderFast(Line[] input){
		int base = getBase(0, input.length-1);
		input = sortByBase(input, 0, input.length - 1, base);
		
		return input;
	}
	
	private static Line[] sortByBase(Line[] input, int start, int end, int base){
		List<Line> bigger = new ArrayList<Line>();
		List<Line> smaller = new ArrayList<Line>();
		for (int i = 0; i < input.length; i++) {
			if (input[i].compareTo(input[base]) > 0) {
				bigger.add(input[i]);
			}else{
				smaller.add(input[i]);
			}
		}
		int j = start;
		for (Line x : smaller) {
			input[j] = x;
			j++;
		}
		for(Line x : bigger){
			input[j] = x;
			j++;
		}
		return input;
	}
	
	private static int getBase(int begin, int end){
		return  (int)Math.floor(end - begin/2);
	}
	
	
	public static void switchElements(Line[] in, int i,int j) {
		Line t = in[i];
		in[i] 	= in[j];
		in[j] = t;
	}

	public static void printLines(Line[] input){
		for (Line line : input) {
			System.out.println("start: " + line.getStart() + " end: " + line.getEnd());
		}
	}
}

@SuppressWarnings("rawtypes")
class Line implements Comparable{
	private int start;
	private int end;
	private int length;

	Line(int start, int end){
		this.start  = start;
		this.end    = end;
		this.length = this.end - this.start;
	}

	int getStart(){
		return this.start;
	}

	int getEnd(){
		return this.end;
	}

	void setStart(int start){
		this.start = start;
	}

	void setEnd(int end){
		this.end = end;
	}
	

	public boolean equals(Object obj){
		if (this == obj) {
			return true;
		}else if (this.getClass() == obj.getClass()) {
			Line objLine = (Line)obj;
			if (this.getStart() == objLine.getStart() && this.getEnd() == objLine.getEnd()){
				return true;				
			}
			return false;
		}else{
			return false;
		}
	}

	int getLength() {
	    return length;
	}

	public int compareTo(Object o) {
		if(o instanceof Line){
			Line line = (Line)o;
			if(this.getStart() == line.getStart() && this.getEnd() == line.getEnd()){
				return 0;
			}else if( this.getStart() > line.getStart()){
				return 1;
			}else if(this. getStart() < line.getStart()){
				return -1;
			}else if(this.getStart() == line.getStart() && this.getEnd() > line.getEnd()){
				return 1;
			}else{
				return -1;
			}
		}else{
			throw new ClassCastException("Can't compare to a non-Line object!");
		}
	}

}